import { Compare, defaultCompare, ICompareFunction } from '../../util';
/**
 * 归并排序(merge-sort)：跟冒泡、选择、插入三种排序方式区别很大，它运用了分而治之的思想。
 * 一直将数组分割成长度近似的两段，直到长度为1不可分割；再将其一一合并，归并的过程中会将左
 * 右两边的元素进行依次排序（从左右分别拿一项进行比较，排好序放入新数组，直到左右其中一个里
 * 元素被取完，而剩余的也会被连接到新数组），最后合并得到的新数组就是排好序的数组。
 * @param array 原数组
 * @param compareFn 比较函数
 * 最差、平均、最好时间复杂度都是O(nlog(n))；空间复杂度是O(n)，因为在每次合并的过程中都
 * 使用了一个临时数组存储。
 */
export function mergeSort<T>(array: T[], compareFn = defaultCompare): T[] {
    // 最后只能分成长度为1的数组
    if (array.length > 1) {
        const middle = Math.floor(array.length / 2);
        // 分解成左侧数组
        const left = mergeSort(array.slice(0, middle), compareFn);
        // 分解成右侧数组
        const right = mergeSort(array.slice(middle, array.length), compareFn);

        // 分解完后去归并，最低可以保证长度为2的有顺序，进而保证长度为3、4、5......都有顺序
        array = merge(left, right, compareFn);
    }

    return array;
}
/**
 * 归并处理
 * @param left 左侧的数组
 * @param right 右侧的数组
 * @param compareFn 比较函数
 */
function merge<T>(left: T[], right: T[], compareFn: ICompareFunction<T>): T[] {
    let i: number = 0;
    let j: number = 0;
    const result: T[] = [];

    // 左右的数组长度差保持在1以内，所有同时遍历它们，直到某一方遍历完，后面再用concat连接没经过遍历的元素
    while (i < left.length && j < right.length) {
        // 从左右数组里取最小的到新数组里，有可能左侧一直比右侧小，没关系，下面用concat连接即可
        result.push(compareFn(left[i], right[j]) === Compare.LESS_THAN ? left[i ++] : right[j ++]);
    }

    // 先slice，因为还有没有遍历过的，后面直接用concat连接，因为剩余的也是有顺序的（之前也merge过了，都是有顺序的）
    return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}
